theoretical computer science Theoretical computer science (TCS) is a subset of general computer science and mathematics that focuses on mathematical aspects of computer science such as the theory of computation, lambda calculus, and type theory. It is difficult to circumsc ...

and

mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...

, especially in the area of

combinatorics on words Combinatorics on words is a fairly new field of mathematics, branching from combinatorics, which focuses on the study of words and formal languages. The subject looks at letters or symbols, and the sequences they form. Combinatorics on words ...

, the Levi lemma states that, for all

strings String or strings may refer to: *String (structure), a long flexible structure made from threads twisted together, which is used to tie, bind, or hang other objects Arts, entertainment, and media Films * ''Strings'' (1991 film), a Canadian anim ...

''u'', ''v'', ''x'' and ''y'', if ''uv'' = ''xy'', then there exists a string ''w'' such that either :''uw = x'' and ''v'' = ''wy'' (if , ''u'', ≤ , ''x'', ) or :''u'' = ''xw'' and ''wv'' = ''y'' (if , ''u'', ≥ , ''x'', ) That is, there is a string ''w'' that is "in the middle", and can be grouped to one side or the other. Levi's lemma is named after

Friedrich Wilhelm Levi Friedrich Wilhelm Daniel Levi (February 6, 1888 – January 1, 1966) was a German mathematician known for his work in abstract algebra, especially torsion-free abelian groups. He also worked in geometry, topology, set theory, and analysis. Early ...

, who published it in 1944.

Applications

Levi's lemma can be applied repeatedly in order to solve word equations; in this context it is sometimes called the Nielsen transformation by analogy with the Nielsen transformation for groups. For example, starting with an equation ''xα'' = ''yβ'' where ''x'' and ''y'' are the unknowns, we can transform it (assuming '', x, ≥ , y, '', so there exists ''t'' such that ''x''=''yt'') to ''ytα'' = ''yβ'', thus to ''tα'' = ''β''. This approach results in a graph of substitutions generated by repeatedly applying Levi's lemma. If each unknown appears at most twice, then a word equation is called quadratic; in a quadratic word equation the graph obtained by repeatedly applying Levi's lemma is finite, so it is decidable if a quadratic word equation has a solution. . A more general method for solving word equations is Makanin's algorithm.

Generalizations

The above is known as the Levi lemma for strings; the lemma can occur in a more general form in

graph theory In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conne ...

and in

monoid theory In mathematics, a semigroup is an algebraic structure consisting of a set together with an associative internal binary operation on it. The binary operation of a semigroup is most often denoted multiplicatively: ''x''·''y'', or simply ''xy ...

; for example, there is a more general Levi lemma for

traces Traces may refer to: Literature * ''Traces'' (book), a 1998 short-story collection by Stephen Baxter * ''Traces'' series, a series of novels by Malcolm Rose Music Albums * ''Traces'' (Classics IV album) or the title song (see below), 1969 * ''Tra ...

originally due to Christine Duboc. Several proofs of Levi's Lemma for traces can be found in ''The Book of Traces''. A monoid in which Levi's lemma holds is said to have the equidivisibility property. The

free monoid In abstract algebra, the free monoid on a set is the monoid whose elements are all the finite sequences (or strings) of zero or more elements from that set, with string concatenation as the monoid operation and with the unique sequence of zero eleme ...

of strings and string concatenation has this property (by Levi's lemma for strings), but by itself equidivisibility is not enough to guarantee that a monoid is free. However an equidivisible monoid ''M'' is free if additionally there exists a

homomorphism In algebra, a homomorphism is a structure-preserving map between two algebraic structures of the same type (such as two groups, two rings, or two vector spaces). The word ''homomorphism'' comes from the Ancient Greek language: () meaning "same" ...

''f'' from ''M'' to the monoid of natural numbers (free monoid on one generator) with the property that the

preimage In mathematics, the image of a function is the set of all output values it may produce. More generally, evaluating a given function f at each element of a given subset A of its domain produces a set, called the "image of A under (or through) ...

of 0 contains only the identity element of ''M'', i.e.

f^(0) = \

. (Note that ''f'' simply being a homomorphism does not guarantee this latter property, as there could be multiple elements of ''M'' mapped to 0.) A monoid for which such a homomorphism exists is also called ''graded'' (and the ''f'' is called a gradation).

Notes

{{Reflist Combinatorics on words Lemmas

Applications

Generalizations

See also

Notes